import collections
from typing import List


class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        graph = collections.defaultdict(set)
        for edge in edges:
            graph[edge[0]].add(edge[1])
            graph[edge[1]].add(edge[0])

        visited = {1: 1}
        queue = collections.deque([1])
        while queue and t >= 0:
            for _ in range(len(queue)):
                n1 = queue.popleft()
                v1 = visited[n1]
                if n1 == target:
                    if t == 0:
                        return v1
                    elif (n1 != 1 and len(graph[n1]) == 1) or (n1 == 1 and len(graph[n1]) == 0):
                        return v1
                    else:
                        return 0

                # 已经到达叶结点的情况
                if n1 != 1 and len(graph[n1]) == 1:
                    continue

                if n1 == 1:
                    v2 = visited[n1] / len(graph[n1])
                else:
                    v2 = visited[n1] / (len(graph[n1]) - 1)

                for n2 in graph[n1]:
                    if n2 not in visited:
                        visited[n2] = v2
                        queue.append(n2)

            t -= 1

        return 0


if __name__ == "__main__":
    # 0.16666666666666666
    print(Solution().frogPosition(n=7, edges=[[1, 2], [1, 3], [1, 7], [2, 4], [2, 6], [3, 5]], t=2, target=4))

    # 0.3333333333333333
    print(Solution().frogPosition(n=7, edges=[[1, 2], [1, 3], [1, 7], [2, 4], [2, 6], [3, 5]], t=1, target=7))

    # 0.16666666666666666
    print(Solution().frogPosition(n=7, edges=[[1, 2], [1, 3], [1, 7], [2, 4], [2, 6], [3, 5]], t=20, target=6))

    # 测试用例3/203 : 1.0
    print(Solution().frogPosition(n=3, edges=[[2, 1], [3, 2]], t=1, target=2))

    # 测试用例198/203 : 1
    print(Solution().frogPosition(n=1, edges=[], t=1, target=1))
